#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int *kmpNext;

void preKmp(char *x, int m) {
   int i, j;

   i = 0;
   j = kmpNext[0] = -1;
   while (i < m) {
      while (j > -1 && x[i] != x[j])
         j = kmpNext[j];
      i++;
      j++;
      if (x[i] == x[j])
         kmpNext[i] = kmpNext[j];
      else
         kmpNext[i] = j;
   }
}

void kmp(char *x, int m, char *y, int n) {
   int i, j;

   /* Preprocessing */
   preKmp(x, m);

   /* Searching */
   i = j = 0;
   while (j < n) {
      while (i > -1 && x[i] != y[j])
         i = kmpNext[i];
      i++;
      j++;
      if (i >= m) {
         printf("%d\n", j - i);
         i = kmpNext[i];
      }
   }
}

void bruteForce(char *x, int m, char *y, int n) {
   int i, j;

   /* Searching */
   for (j = 0; j <= n - m; ++j) {
      for (i = 0; i < m && x[i] == y[i + j]; ++i);
      if (i >= m)
         printf("%d\n", j);
   }
}

void copia(FILE *f, char *v, int tam){
    int i;
    rewind(f);
    for(i = 0; i < tam; i++){
        v[i] = fgetc(f);
    }
}

int main()
{
    FILE *pattern, *texto;      // arquivos de texto (modelos)
    pattern = fopen("pattern.txt", "r+t");
    texto = fopen("texto.txt", "r+t");

    fseek(pattern, 0, SEEK_END);    // calcula tamanho do arquivo pattern.txt
    int m = ftell(pattern);         // tamanho do vetor pat (string a ser procurada)
    kmpNext = (int *) malloc (m * sizeof(int));     // aloca o vetor usado no algoritmo KMP com o tamanho de m

    fseek(texto, 0, SEEK_END);
    int n = ftell(texto);           // tamanho do vetor tex (string na qual "pat" será procurada)

    char *pat, *tex;    // vetores que conterão a informação dos arquivos

    pat = (char *) malloc (m * sizeof(char));
    tex = (char *) malloc (n * sizeof(char));

    copia(pattern, pat, m);     // passa os arquivos para os vetores
    copia(texto, tex, n);

    clock_t start, end;
    int i;

    FILE *brute, *km;   // arquivos texto com os tempos de execução de cada algoritmo
    brute = fopen("BRUTEFORCE.txt", "w+t");
    km = fopen("KMP.txt", "w+t");

    // início dos testes
    for(i = 0; i < 100; i++){
        start = clock();
        bruteForce(pat, m, tex, n);
        end = clock();
        fprintf(brute, "%d,%f\n", i, (float)(end - start)/CLOCKS_PER_SEC);
    }system("clear");

    for(i = 0; i < 100; i++){
        start = clock();
        kmp(pat, m, tex, n);
        end = clock();
        fprintf(km, "%d,%f\n", i, (float)(end - start)/CLOCKS_PER_SEC);
    }system("clear");


    // fechamento de tudo
    fclose(pattern);
    fclose(texto);
    fclose(brute);
    fclose(km);
    free(pat);
    free(tex);
    free(kmpNext);
    return 0;
}
